#ifndef xpack_test_algo_binary_search
#define xpack_test_algo_binary_search
#pragma push_macro("xuser")
#undef  xuser
#define xuser mixc::test_algo_binary_search::inc
#include"test/helper.hpp" // 需要放第一
#include"algo/binary_search.hpp"
#include"interface/seqptr.hpp"
#include"utils/array.hpp"
#include"math/random.hpp"
#pragma pop_macro("xuser")

#ifndef xtest_algo_binary_search_deepth
#define xtest_algo_binary_search_deepth     128
#endif

namespace mixc::test_algo_binary_search{
    xtest("binary_search") {
        using namespace inc;
        array<uxx, xtest_algo_binary_search_deepth> c;

        auto search = [&](uxx length, auto target, auto mode){
            if (length == 0){
                return not_exist;
            }
            for (uxx i = 0; i < length; i++){
                if (c[i] == target){
                    return i;
                }
                if (c[i] > target){
                    switch(mode){
                    case 0: break;
                    case 1: return i - 1;   // less_equals
                    case 2: return i;       // grater_equals
                    }
                }
            }
            if (mode == 1 && c[length - 1] < target){
                return length - 1;
            }
            return not_exist;
        };

        // 生成用例
        for (uxx i = 0; i < c->length; i++){
            c[i] = i * 2 + 1;
        }

        uxx actual;
        uxx wanted;

        // 对比测试
        for(uxx length = 0; length <= c->length; length++){
            auto r = seqptr<uxx>(c).subseq(co{0, length});

            for (uxx find = 0; find < length * 2 + 2; find++){
                actual = inc::binary_search::match(r, find);
                wanted = search(length, find, 0);
                xassert(actual == wanted or c[actual] == c[wanted], length, find, actual, wanted);

                actual = inc::binary_search::less_equals(r, find);
                wanted = search(length, find, 1);
                xassert(actual == wanted or c[actual] == c[wanted], length, find, actual, wanted);

                actual = inc::binary_search::greater_equals(r, find);
                wanted = search(length, find, 2);
                xassert(actual == wanted or c[actual] == c[wanted], length, find, actual, wanted);
            }
        }

        c[0] = 1;

        for(uxx length = 0; length <= c->length; length += (length + 2) / 2){
            for(uxx t = 0; t < 0x100000; t++){
                for(uxx i = 1; i < length; i++){
                    if (inc::random<bool>()){ // bit 为 1 表示比前一个大
                        c[i] = c[i - 1] + 2;
                    }
                    else{ // 否则持平
                        c[i] = c[i - 1];
                    }
                }

                for(uxx i = 0; i <= length; i++){
                    auto find = i * 2;
                    auto r = seqptr<uxx>(c).subseq(co{0, length});
                    actual = inc::binary_search::match(r, find);
                    wanted = search(length, find, 0);
                    xassert(actual == wanted or c[actual] == c[wanted], length, find, actual, wanted);

                    actual = inc::binary_search::less_equals(r, find);
                    wanted = search(length, find, 1);
                    xassert(actual == wanted or c[actual] == c[wanted], length, find, actual, wanted);

                    actual = inc::binary_search::greater_equals(r, find);
                    wanted = search(length, find, 2);
                    xassert(actual == wanted or c[actual] == c[wanted], length, find, actual, wanted);

                    actual = inc::binary_search::first_greater_equals(r, find);
                    wanted = search(length, find, 2);

                    // 避免条件前置，因为 actual 可能为 -1，导致 sanity 检查失败
                    // auto is_lower_bound = c[actual] == c[wanted] and (actual == 0 ? true : c[actual] != c[actual - 1]);
                    if (actual != wanted){
                        if (actual == not_exist or wanted == not_exist){
                            xhint(actual, wanted);
                        }
                        xassert(c[actual] == c[wanted] and (actual == 0 ? true : c[actual] != c[actual - 1]),
                            length, find, actual, wanted
                        );
                    }
                    else{
                        xassert(true);
                    }

                    actual = inc::binary_search::last_less_equals(r, find);
                    wanted = search(length, find, 1);

                    if (actual != wanted){
                        if (actual == not_exist or wanted == not_exist){
                            xhint(actual, wanted);
                        }
                        xassert(c[actual] == c[wanted] and (actual == length - 1 ? true : c[actual] != c[actual + 1]), length, find, actual, wanted);
                    }
                    else{
                        xassert(true);
                    }
                }
            }
        }
    };
}

#endif
